The present invention relates to a device and method for efficient computation of Voronoi Diagrams of General Generators in General Spaces and to uses thereof in technology and, more particularly, but not exclusively to uses thereof in communications networks, in robotics, in three-dimensional networks, in materials science, in molecular biology, in searching of data, in a way of providing overall control of a variety of methods for applications such as image processing, data categorization, numerical simulations, meshing, solid modeling, clustering etc, efficient designs of electronic circuits, for management of graphical information systems, efficient location problems, face recognition and image recognition in general, as an artistic tool, and as a programming tool,
Voronoi diagrams (Dirichlet's tessellations) are one of the basic structures in computational geometry. Roughly speaking, they are a certain decomposition of a given space X into cells, induced by a tuple of subsets (Pk)kεK, called the generators or the sites, and by a distance function. More precisely, the k-th Voronoi cell is the set of all the points in X whose distance to Pk is not greater than their distance to the union of the other generators Pj. They are named after Georgy Voronoi, and may also be referred to as a Voronoi tessellation, a Voronoi decomposition, or a Dirichlet tessellation (after Lejeune Dirichlet),
Voronoi diagrams appear in a huge number of places in science and technology and have many applications. One can find them and their applications in chemistry, biology, archeology, image processing, computational geometry, crystallography, geography, metallography, economics, art, computer science, astronomy, linguistics, robotics, communication and many more places.
In the simplest case, we are given a set of points S in the plane, which are the Voronoi sites. Each site s has a Voronoi cell, also called a Dirichlet cell, V(s) consisting of all points in the plane whose distance to s is not greater than their distance to any other site. Bisectors of the Voronoi diagram are all the points in the plane that are equidistant to two sites. The Voronoi vetices are the points equidistant to three or more sites. FIG. 1 illustrates a Voronoi diagram of a random set of points in a plane, showing points, sites, bisectors and vertices.
A very simple real world illustration of Voronoi diagrams is demonstrated by the following example. Let P—1, . . . ,P_n represent n shops in some city/district, where each P_k represents a single shop. The k-th Voronoi cell is the collection of all the points in the city for which the k-th shop is the closest one. Hence, if the potential costumers choose their preferred shop based on the geographical distance, the k-th Voronoi cell can be used to estimate roughly the size of the set of the potential costumers of the k-th shop. If costumers measure their preferences by some other distance functions, say the l—1 (Manhattan) distance, by a distance which takes into account the topography, or by some mixed distance which takes into account also price considerations, then the Voronoi diagram may be changed drastically. As a further realistic generalization, we may think of P_k as representing a firm of shops, and hence allow it to include several shops. We may also allow the case where P_k and P_j have a nonempty intersection, and this represents the case where two competitor shops are located in the same place (e.g., in a shopping center).
Having all of the above in mind, it can be seen that developing methods for computing Voronoi diagrams is therefore an important task. Many such methods have been published and implemented in the last decades. Among them we mention the naive method, the divide-and-conquer method, the incremental method the plane sweep method, methods which make use of lower envelope, and methods based on geometric transforms. However, these methods are for specific cases. They impose restrictions on either the space X, the generators (Pk)K, the distance function d, and sometimes even impose a priory assumptions on the behavior of the Voronoi cells themselves. The most studied case is the Euclidean plane, with a finite set of generators, each one represents a distinct point. A typical method which generalizes this case usually assumes that two or three of the four components of the quartet (X, d, (Pk)K, K) are simple, and then tries to generalize the other one(s). For example, it assumes that the quartet is the Euclidean plane with a finite set of distinct line segments/balls, the m-dimensional Euclidean space with a finite set of distinct points, or the plane with the l1 distance and a finite set of distinct line segments.
As far as we know, all known methods assume that K is finite and that the generators are connected. In addition, with the exception of a few studies, (e.g., n possibly intersecting discs in R^2), it is assumed that the generators are disjoint. Moreover, the generators are simple in some sense. For example, they are assumed to be special curves, e.g., line segments or circular arcs, special surfaces, e.g., spheres, or some other special shapes such as polygons or balls.
One of the characteristics of the known methods is that they suffer from degenerate cases, from stability problems due to numerical errors, and that their success is not always fully proved. This is especially true when the generators are not assumed to be distinct points, or (X, d) is not assumed to be the Euclidean plane. Another characteristic is that their implementation is quite complicated, for example because one has to take into account all the degenerate cases. A third characteristic is that with the exception of few cases, such as the naive method with restricted assumptions, one cannot compute the k-th Voronoi cell independently of the other cells, a property which imposes difficulties on attempts to make parallel computations of Voronoi diagrams or to update the diagram when only some of the generators are changed. (However, such attempts do exist.) A fourth characteristic is that most of the methods compute the exact Voronoi diagram, by computing the exact boundary of the corresponding cells. This is done either directly, or by computing a dual concept (Delaunay triangulation). The resulting Voronoi diagram is however also approximated, either because of numerical errors, or because some approximations are made during their implementation.
We note that there are some methods which try to approximate the Voronoi diagram. We mention two. The first is the digital plane method which is a brute force method; it is for grids. It does not impose any restriction on the distance function or on the generators, which are assumed to consists of finitely many points, but however it is slow and in practice it is used for grids in R^2, and sometimes in R^3. The second method is based on octrees and is for generators of a general form in Euclidean spaces. We have not been able to determine some of its properties, such as its efficiency or the simplicity of its implementation in practice.